The diversity and versatility of print and display devices imposes demands on designers of multimedia content for rendering and viewing. For instance, designers must provide different alternatives for web-content, and design different layouts for different rendering applications and devices, ranging from tiny “thumbprints” of images often seen in selections menus, small, low resolution mobile telephone screens, slightly larger PDA screens, to large, high resolution elongated flat panel displays, and projector screens. Adapting images to different rendering applications and devices than originally intended is called image retargeting.
Conventional image editing by retargeting typically involves scaling and cropping. Image scaling is insufficient because it ignores the image content and typically can only be applied uniformly. Scaling also does not work well when the aspect ratio of the image needs to change, because it introduces visual distortions. Cropping is limited because it can only remove pixels from the image periphery. More effective resizing can only be achieved by considering the image content as a whole, in conjunction with geometric constraints of the output device.
While resizing an image, there is a desire to change the size of the image while maintaining important features in the content of the image. This can be done with top-down or bottom-up methods. Top-down methods use tools such as face detectors to detect important regions in the image, whereas bottom-up methods rely on visual saliency methods to construct visual saliency map of the source image. After the saliency map is constructed, cropping can be used to display the most important region of the image, see U.S. Pat. No. 7,477,800—Avidan et al, and PCT/U.S. Patent Application 08/83252—Rubenstein et al.
Other editing methods can be based on image contours. Discrete programming can be used to detect the contours in images, Montanari, “On the optimal detection of curves in noisy pictures,” Communications of the ACM, 14(5):335-345, 1971. The use of such contours for image edits originates with intelligent scissors, Mortensen et al., “Intelligent scissors,” Proc. SIGGRAPH, 1995, and for composing new pixel adjacencies in texture synthesis, Efros et al., “Image quilting for texture synthesis and transfer,” Proc. SIGGRAPH, 2001, and Kwatra et al., “Image and video synthesis using graph cuts,” Proc. SIGGRAPH, 2003. The Efros et al. and Kwatra et al. use contours where the image has minimal contrast; these are called seams.
Avidan et al., see above, describe carving away pixels along a low contrast image-spanning seam to narrow an image by one column or row. Doing so repeatedly yields a very striking animation. There is no penalty for distortions, but if no seam transects foreground scene objects, these are left intact. The method is very simple and fast. However, seam carving often distorts and damages image contours. The seams are not optimal for the target image dimensions, and a greedy sequential strategy precludes the use for videos. Rubenstein et al., use a graph-cut reformulation that handles video, but the optimizer is impractically slow and still limited to greedy seam removal.
Another method describes linear or quadratic penalties for squeezing pixels together, Wolf et al., “Non-homogeneous content-driven video-retargeting,” Proc. ICCV, 2007. The quadratic version is solved by the same sparse least-squares computation that gives weighted Tutte embeddings of graphs in the plane, see Tutte, “How to draw a graph,” Proc. London Mathematical Society, 13(1):743-767, 1963. However, that method is vulnerable to unwanted embedding “catastrophes” where regions of the image invert and overlap over other regions, i.e., the pixel order is not necessarily preserved.
Image editing can also be performed partitioning and an image into segments, and recompositing the segments in visually pleasing ways, Setlur et al., “Automatic image retargeting,” Proc. Mobile and Ubiquitous Multimedia, 2005, Simakov et al., “Summarizing visual data using bidirectional similarity,” Proc. CVPR, and Cho et al., “The patch transform and its applications to image editing,” CVPR, 2008.
Other image editing functions include removing and adding objects to images or videos.